#pragma once

#include "SLList.h"

#define HASHBUCKETNUMBER 100

////////////////////////////////////////////////////////////////////////////////////////////////////
/// <Summary>	Dictionary  </Summary>
/// 
/// <purpose>	Key based container used for quick look up	</purpose>
////////////////////////////////////////////////////////////////////////////////////////////////////

template <typename K, typename T>
class Dictionary
{
	struct Node
	{
		K key;
		T data;
	};

public:

	class Iterator
	{
		friend class Dictionary<K,T>;

		Dictionary<K,T>* dictionary;

		typename SLList<typename Dictionary<K,T>::Node>::Iterator iter;

		typename Dictionary<K,T>::Node* curr;

		unsigned int currBucket;

	public:

		Iterator(Dictionary<K,T>& dictionaryToIterate);

		void Begin();

		bool End();

		Iterator& operator++();

		typename Dictionary<K,T>::Node& operator*();
	};

private:

	unsigned int (*hasher)(const K&);
	SLList<Node>* buckets;

public:

	Dictionary(unsigned int (*hasherfunc) (const K&));

	~Dictionary();

	Dictionary& operator=(const Dictionary& ref);

	Dictionary(const Dictionary& ref);

public:

	void Clear();

	void Insert(const K& key, const T& data);

	void Erase(const K& key);

	void Erase(typename Dictionary<K,T>::Iterator& index);

	T& operator[](const K& key);

};









template <typename K, typename T>
Dictionary<K,T>::Dictionary(unsigned int (*hasherfunc) (const K&))
{
	hasher = hasherfunc;
	buckets = new SLList<Node>[HASHBUCKETNUMBER];
}

template <typename K, typename T>
Dictionary<K,T>::~Dictionary()
{
	Clear();
	delete[] buckets;
}

template <typename K, typename T>
Dictionary<K,T>::Dictionary(const Dictionary& ref)
{
	hasher = ref.hasher;

	buckets = new SLList<Node>[HASHBUCKETNUMBER];

	for( unsigned i = 0; i < HASHBUCKETNUMBER; ++i )
		buckets[i] = ref.buckets[i];
}

template <typename K, typename T>
Dictionary<K,T>& Dictionary<K,T>::operator=(const Dictionary& ref)
{
	if(this != &ref)
	{
		Clear();
		delete[] buckets;

		hasher = ref.hasher;

		buckets = new SLList<Node>[HASHBUCKETNUMBER];

		for( unsigned i = 0; i < HASHBUCKETNUMBER; ++i )
			buckets[i] = ref.buckets[i];
	}

	return *this;
}

template <typename K, typename T>
void Dictionary<K,T>::Clear()
{
	for(unsigned i = 0; i < HASHBUCKETNUMBER; ++i)
		buckets[i].Clear();
}

template <typename K, typename T>
void Dictionary<K,T>::Insert(const K& key, const T& data)
{
	unsigned int hashnum = hasher(key);
	hashnum %= HASHBUCKETNUMBER;

	SLList<Node>::Iterator iter(buckets[hashnum]);
	for(; !iter.End(); ++iter)
	{
		if((*iter).key == key)
		{
			(*iter).data = data;
		}
	}

	Node node;
	node.key = key;
	node.data = data;
	buckets[hashnum].Push_Front(node);
}

template <typename K, typename T>
void Dictionary<K,T>::Erase(const K& key)
{
	unsigned int hashnum = hasher(key);
	hashnum %= HASHBUCKETNUMBER;

	SLList<Node>::Iterator iter(buckets[hashnum]);
	for(; !iter.End(); ++iter)
	{
		if((*iter).key == key)
		{
			buckets[hashnum].Erase(iter);
			break;
		}
	}
}

template <typename K, typename T>
void Dictionary<K,T>::Erase(typename Dictionary<K,T>::Iterator& index)
{
	SLList<Node>::Iterator iter(buckets[index.currBucket]);
	for(; !iter.End(); ++iter)
	{
		if((*iter).key == index.curr->key)
		{
			buckets[index.currBucket].Erase(iter);
			break;
		}
	}
}

template <typename K, typename T>
T& Dictionary<K,T>::operator[](const K& key)
{
	unsigned int hashnum = hasher(key);
	hashnum %= HASHBUCKETNUMBER;

	SLList<Node>::Iterator iter(buckets[hashnum]);
	for(; !iter.End(); ++iter)
	{
		if((*iter).key == key)
		{
			return (*iter).data;
		}
	}

	Node node;
	node.key = key;
	buckets[hashnum].Push_Front(node);
	iter.Begin();
	return (*iter).data;
}









template <typename K, typename T>
Dictionary<K,T>::Iterator::Iterator(Dictionary<K,T>& dictionaryToIterate)
	: dictionary(&dictionaryToIterate), iter(dictionary->buckets[0])
{
	this->Begin();
}

template <typename K, typename T>
void Dictionary<K,T>::Iterator::Begin()
{
	SLList<Dictionary<K,T>::Node>::Iterator iter(dictionary->buckets[0]);

	curr = &(*iter);

	currBucket = 0;

	if(iter.End())
	{
		for(;;)
		{
			currBucket++;

			if(currBucket >= HASHBUCKETNUMBER)
			{
				curr = NULL;
				return;
			}

			iter.ChangeList(dictionary->buckets[currBucket]);

			if(!iter.End())
			{
				curr = &(*iter);
				return;
			}
		}
	}
}

template <typename K, typename T>
bool Dictionary<K,T>::Iterator::End()
{
	if(curr)
		return false;
	else
		return true;
}

template <typename K, typename T>
typename Dictionary<K,T>::Iterator& Dictionary<K,T>::Iterator::operator++()
{
	++iter;

	if(iter.End())
	{
		for(;;)
		{
			currBucket++;

			if(currBucket >= HASHBUCKETNUMBER)
			{
				curr = NULL;
				return *this;
			}

			iter.ChangeList(dictionary->buckets[currBucket]);

			if(!iter.End())
			{
				break;
			}
		}
	}

	curr = &(*iter);
	return *this;
}

template <typename K, typename T>
typename Dictionary<K,T>::Node& Dictionary<K,T>::Iterator::operator*()
{
	return *curr;
}